import type { Edge } from '@xyflow/react';
import { type BehaviorTreeNode, NodeType } from '../types/behaviorTree';

/**
 * @interface ValidationError
 * @description 定义行为树验证错误的接口，用于描述在验证行为树结构时发现的单一问题。
 * @property {string} [nodeId] - 导致此错误的节点 ID (可选)。如果错误与特定节点相关，则提供此字段。
 * @property {string} [edgeId] - 导致此错误的边 ID (可选)。如果错误与特定连接相关，则提供此字段。
 * @property {'error' | 'warning'} type - 错误的类型。'error' 表示严重问题，阻止行为树的正常运行；'warning' 表示建议性问题，但不阻止运行。
 * @property {string} message - 错误的详细描述信息，向用户清晰地说明问题所在。
 */
export interface ValidationError {
    nodeId?: string;
    edgeId?: string;
    type: 'error' | 'warning';
    message: string;
}

/**
 * @function validateTree
 * @description 验证行为树的结构是否符合预设规则。此函数执行一系列检查，以确保行为树的逻辑完整性和正确性。
 *              验证规则包括：唯一根节点、无孤立节点、无循环、以及各节点类型的子节点数量约束。
 * @param {BehaviorTreeNode[]} nodes - 行为树中所有节点的数组，包含它们的 ID、类型和数据。
 * @param {Edge[]} edges - 行为树中所有边的数组，定义了节点之间的父子关系。
 * @returns {ValidationError[]} 包含所有发现错误的数组。如果行为树结构完全有效，则返回空数组。
 */
export function validateTree(nodes: BehaviorTreeNode[], edges: Edge[]): ValidationError[] {
    const errors: ValidationError[] = [];

    // 规则 1: 唯一根节点验证
    // 根节点定义为没有任何入边 (in-coming edges) 的节点。一个有效的行为树必须有且仅有一个根节点。
    const nodesWithIncomingEdges = new Set(edges.map(edge => edge.target));
    const rootNodes = nodes.filter(node => !nodesWithIncomingEdges.has(node.id));

    if (rootNodes.length === 0) {
        // 如果没有找到根节点，则报告错误。
        errors.push({
            type: 'error',
            message: '行为树必须有一个根节点。',
        });
    } else if (rootNodes.length > 1) {
        // 如果找到多个根节点，则为每个额外的根节点报告错误。
        rootNodes.forEach(node => {
            errors.push({
                nodeId: node.id,
                type: 'error',
                message: `节点 "${node.data.label}" 是一个根节点，但行为树只能有一个根节点。`,
            });
        });
    }

    // 规则 2: 无孤立点验证 (除了根节点)
    // 孤立节点是指除了根节点外，没有任何入边和出边连接到树中的节点。
    const connectedNodeIds = new Set([...edges.map(edge => edge.source), ...edges.map(edge => edge.target)]);
    
    nodes.forEach(node => {
        // 如果节点不是根节点，并且既没有入边也没有出边，则认为是孤立节点。
        if (!rootNodes.includes(node) && !connectedNodeIds.has(node.id)) {
            errors.push({
                nodeId: node.id,
                type: 'error',
                message: `节点 "${node.data.label}" 是孤立的，没有父节点或子节点。`,
            });
        }
    });

    // 规则 3: 无循环验证
    // 使用深度优先搜索 (DFS) 算法检测有向图中是否存在循环。
    const adjList = new Map<string, string[]>(); // 用于表示图的邻接列表，key为节点ID，value为该节点的所有子节点ID数组。
    nodes.forEach(node => adjList.set(node.id, [])); // 初始化每个节点的邻接列表为空。
    edges.forEach(edge => {
        const children = adjList.get(edge.source);
        if (children) {
            children.push(edge.target); // 添加从 source 到 target 的有向边。
        }
    });

    const visited = new Set<string>(); // 记录在 DFS 遍历中已经访问过的所有节点，防止重复遍历。
    const recursionStack = new Set<string>(); // 记录当前 DFS 递归路径上的节点。如果遇到一个在 recursionStack 中的节点，则表示存在循环。

    /**
     * @function getNodeLabel
     * @description 根据节点 ID 获取节点的显示标签。
     * @param {string} id - 节点的 ID。
     * @returns {string} 节点的标签或其 ID (如果标签不存在)。
     */
    const getNodeLabel = (id: string) => nodes.find(n => n.id === id)?.data.label || id;
    const reportedCycles = new Set<string>(); // 用于记录已经报告过的循环，避免重复错误提示。

    /**
     * @function detectCycle
     * @description 递归函数，用于从给定节点开始，深度优先搜索图中是否存在循环。
     * @param {string} nodeId - 当前正在访问的节点 ID。
     * @returns {boolean} 如果从当前节点开始的路径中检测到循环，则返回 true；否则返回 false。
     */
    function detectCycle(nodeId: string): boolean {
        visited.add(nodeId); // 将当前节点标记为已访问。
        recursionStack.add(nodeId); // 将当前节点添加到递归栈中。

        const neighbors = adjList.get(nodeId) || []; // 获取当前节点的所有子节点。
        for (const neighborId of neighbors) {
            if (!visited.has(neighborId)) {
                // 如果邻居节点尚未被访问，则递归访问它。
                if (detectCycle(neighborId)) {
                    const cycleId = [nodeId, neighborId].sort().join('_'); // 生成一个唯一的循环标识符。
                    if (!reportedCycles.has(cycleId)) {
                        errors.push({
                            type: 'error',
                            message: `行为树中存在循环，涉及节点 "${getNodeLabel(nodeId)}" 和 "${getNodeLabel(neighborId)}"。`,
                            nodeId: nodeId // 可以在错误中包含导致循环的节点ID。
                        });
                        reportedCycles.add(cycleId);
                    }
                    return true; // 发现循环，立即返回 true。
                }
            } else if (recursionStack.has(neighborId)) {
                // 如果邻居节点已被访问且在当前递归栈中，则说明存在循环。
                const cycleId = [nodeId, neighborId].sort().join('_'); // 生成一个唯一的循环标识符。
                if (!reportedCycles.has(cycleId)) {
                    errors.push({
                        type: 'error',
                        message: `行为树中存在循环，涉及节点 "${getNodeLabel(nodeId)}" 和 "${getNodeLabel(neighborId)}"。`,
                        nodeId: nodeId // 可以在错误中包含导致循环的节点ID。
                    });
                    reportedCycles.add(cycleId);
                }
                return true; // 发现循环，立即返回 true。
            }
        }
        recursionStack.delete(nodeId); // 当前节点及其子树访问完毕，从递归栈中移除。
        return false; // 未发现循环。
    }

    // 对每个未访问的节点进行 DFS，以确保遍历所有连通分量，从而发现图中所有的循环。
    for (const node of nodes) {
        if (!visited.has(node.id)) {
            detectCycle(node.id);
        }
    }

    // 规则 4: 父子数量约束
    // 不同的行为树节点类型对其子节点的数量有特定的限制。
    const childCounts = new Map<string, number>(); // 记录每个父节点的子节点数量。
    edges.forEach(edge => {
        childCounts.set(edge.source, (childCounts.get(edge.source) || 0) + 1);
    });

    nodes.forEach(node => {
        const count = childCounts.get(node.id) || 0; // 获取当前节点的子节点数量。
        switch (node.type) {
            case NodeType.Decorator:
                // 装饰器节点 (Decorator) 必须且只能有一个子节点。
                if (count !== 1) {
                    errors.push({
                        nodeId: node.id,
                        type: 'error',
                        message: `装饰器节点 "${node.data.label}" 必须且只能有一个子节点。`,
                    });
                }
                break;
            case NodeType.Action:
            case NodeType.Condition:
                // 动作节点 (Action) 和条件节点 (Condition) 是叶子节点，不能有子节点。
                if (count > 0) {
                    errors.push({
                        nodeId: node.id,
                        type: 'error',
                        message: `叶子节点 "${node.data.label}" (动作/条件) 不能有子节点。`,
                    });
                }
                break;
            case NodeType.Sequence:
            case NodeType.Selector:
                // 组合节点 (Sequence, Selector) 建议至少有一个子节点。如果子节点数量为0，则作为警告而非错误，因为它可能是中间状态。
                if (count === 0) {
                    errors.push({
                        nodeId: node.id,
                        type: 'warning',
                        message: `组合节点 "${node.data.label}" (顺序/选择) 建议至少有一个子节点。`,
                    });
                }
                break;
            default:
                // 对于未知或未明确约束的节点类型，不添加验证错误，保持灵活性。
                break;
        }
    });

    return errors;
}